/*
 1:借助并查集来实现，有两个数组，一个是并查集的数组，一个是边的数组，但是现在写的还不是很完整，现在写的只是找出了最小的边，但是没有组成树，组成树还是要用到树的存储结构，其实这个也好写，就是在树的数组中添加结点就好了
 */
#include <iostream>
using namespace std;
typedef struct node  {
    int start;//边的起点
    int end;//边的终点
    int wieght;//边的权重
}node;
class Graph{
private:
    node *edge; //边的数组
    int edgeNum;//边的个数
    int vertexNum;//顶点的个数
    int* unionset;//并查集，顶点的集合
#pragma 下面的这几个private函数都是并查集的函数
    int findRoot(int node);//找根
    void unionSet(int node1,int node2);//合并俩结点成为一个集合
    bool isaSet(int node1,int node2);//判断俩结点在没在一个集合中
public:
    Graph(int size,int vertexNum);
    void create();
    void sort();//冒泡法按照权值从大到小的顺序排序；
    void kuscal();//kruskal算法；
    void print();//输出边的数组和 顶点的集合，
};
void Graph::print(){
    cout<<"unionSet-----------------------------------------------------\n";
    for (int i = 0; i<vertexNum+1; i++) {
        cout<<i<<":"<<unionset[i]<<endl;
    }
    cout<<"unionset______________________________________________________\n";
    
    for (int i =0; i<2; i++) {
        cout<<endl;
    }
    cout<<"edge----------------------------------------------------------\n";
    for (int i = 0; i<edgeNum; i++) {
        cout<<"("<<edge[i].start<<","<<edge[i].end<<","<<edge[i].wieght<<")";
    }
    cout<<endl;
    cout<<"edge__________________________________________________________\n";
}
//看是否在同一个集合，如果在一个集合，返回True，否则返回false；
bool  Graph::isaSet(int node1, int node2){
    return findRoot(node1)==findRoot(node2) ? true : false;
}


//把node2添加到node1集合中
void Graph::unionSet(int node1, int node2){
    int root1 = findRoot(node1);
    int root2 = findRoot(node2);
    unionset[root1]+=unionset[root2];
    unionset[root2] = root1;
}


void Graph::sort(){
    for (int i = 0; i<edgeNum -1; i++) {
        for (int j = 0; j<edgeNum-1-i; j++) {
            if(edge[j].wieght < edge[j+1].wieght){
                int temp = edge[j].wieght;
                int start = edge[j].start;
                int end = edge[j].end;
                edge[j].wieght = edge[j+1].wieght;
                edge[j+1].wieght = temp;
                
                edge[j].start = edge[j+1].start;
                edge[j+1].start = start;
                
                edge[j].end = edge[j+1].end;
                edge[j+1].end = end;
            }
        }
    }
    print();
}

int Graph::findRoot(int node){
    int root = node;
    while (unionset[root] >= 0) {
        root = unionset[root];
    }
    return  root;
}

Graph::Graph(int size,int vertexNum){
    edge = new node[size];
    edgeNum = size;
    this->vertexNum = vertexNum;
    /*
     1:一般来说，多申请一个，这样有利于数据的统一
     */
    unionset = new int[vertexNum+1];
    for (int i = 0; i<vertexNum+1; i++) {
        unionset[i]= -1;
    }
}

void Graph::create(){
    cout<<"input edge start and end and widght\n";
    for (int i = 0; i<edgeNum; i++) {
        cin>>edge[i].start>>edge[i].end>>edge[i].wieght;
    }

}
void Graph::kuscal(){
    sort();
    int edgeNum1 = 0;//找到的满足要求的边的个数
    int sum = 0;//找的满足要求的边的权重和
    int i = edgeNum-1;//控制边数组的下标，从后往前取，最小值在后面
    while (edgeNum1 != this->vertexNum-1 ) {
        int start = edge[i].start;
        int end = edge[i].end;
        
        if( isaSet(start, end) == false){
            unionSet(start, end);
            edgeNum1++;
            sum+=edge[i].wieght;
        }
        i--;
    }
    cout<<"sum"<<sum<<endl;
}
int main(){
    Graph a(8, 6);
    a.create();
    a.print();
    a.kuscal();
    a.print();
}
